package com.felight.ems.sort;
class Sorting{
	static int largest;
	static int n;
	
	public static void main(String[] args){
		
		int[] arr={5, 8, 1, 3, 2, 4,0, 78,99,10,20,11};
		double[] array=generateRandomDoubleArray(10000);
		long starti = System.currentTimeMillis();
		insertionSort(array);
		long endi = System.currentTimeMillis();
		System.out.println("Insertion Sort:"+(endi-starti));
		System.out.println();
		long starts = System.currentTimeMillis();
		selectionSort(array,array.length);
		long ends = System.currentTimeMillis();
		System.out.println("Selection Sort:"+(ends-starts));
		System.out.println();
		long startb=System.currentTimeMillis();
		bubbleSort(array,array.length);
		long endb = System.currentTimeMillis();
		System.out.println("Bubble Sort:"+(endb-startb));
		System.out.println();
		long startq = System.currentTimeMillis();
		quickSort(array,0,array.length-1);
		long endq = System.currentTimeMillis();
		System.out.println("Quick Sort:"+(endq-startq));
		System.out.println();
		long starth = System.currentTimeMillis();
		heapSort(array);
		long endh = System.currentTimeMillis();
		System.out.println("Heap Sort:"+(endh-starth));
		System.out.println();
		long startm = System.currentTimeMillis();
		mergeSort(array,0,array.length-1);
		long endm = System.currentTimeMillis();
		System.out.println("Merge Sort:"+(endm-startm));
		System.out.println();
		long startbi=System.currentTimeMillis();//call either binary search or linear search(call them separately), do not call both method simultaneously for same array of elements
		binarySearch(arr,12);
		long endbi = System.currentTimeMillis();
		System.out.println("Binary Search:"+(endbi-startbi));
		System.out.println();
		long startl=System.currentTimeMillis();
		linearSearch(arr,99);
		long endl = System.currentTimeMillis();
		System.out.println("Linear Search:"+(endl-startl));
		System.out.println();
	}
	
	public static void printNumbers(double[]  array){
		
		for(int i=0;i<array.length;i++){
			System.out.print(array[i]+"\t ");
		}
		System.out.println("\n");
	}
	
	public static double[] generateRandomDoubleArray(int size) {
		double[] result=new double[size];
		for(int i=0;i<size;i++)
			result[i]=(int)(Math.random()*1000);
			return result;
	}
	

	
	public static void insertionSort(double[] array){
		for(int i=1;i<array.length;i++){
			double key=array[i];
			int j=i-1;
			while((j> -1)&&(array[j]>key)){
				array[j+1]=array[j];
				j--;
			}
			array[j+1]=key;
		}
		
	}
	

	public static void bubbleSort(double array[],int n){
		int i,j;
		double temp=0.0;
		for(i=0;i<n;i++){
			for(j=1;j<(n-i);j++){
				if(array[j-1]>array[j]){
					temp=array[j-1];
					array[j-1]=array[j];
					array[j]=temp;
				}
			}
		}
	}
	
	
	
	public static void selectionSort(double array[], int n){
		for(int i=0; i<n; i++){
			int min = i;
			for(int j=i; j<n; j++){
				if(array[min]>array[j]){
					min = j;
				}
			}
			double temp = array[i];
			array[i] = array[min];
			array[min] = temp;
		}
		
		
	}
	
	public static void heapSort(double[] array){
		
		buildHeap(array);
		for(int i=n;i>0;i--){
			exchange(array,0,i);
			n=n-1;
			maxHeap(array,0);
		}
		
	}
	public static void buildHeap(double[] array){
		n=array.length-1;
		for(int i=n/2;i>=0;i--)
			maxHeap(array,i);
		
	}
	public static void maxHeap(double[] array,int i){
		int left=2*i;
		int right=2*i+1;
		
		if(left<=n && array[left]>array[i]){
			largest=left;
		}
		else{
			largest=i;
		}
		if(right<=n && array[right]>array[largest]){
			largest=right;
		}
		if(largest!=i){
			exchange(array,i,largest);
			maxHeap(array,largest);
		}
	}
	public static void exchange(double[] array,int i,int j){
		double t=array[i];
		array[i]=array[j];
		array[j]=t;
	}
	public static void quickSort(double[] array,int p,int r){
		if(p<r){
			int q=partition(array,p,r);
			quickSort(array,p,q);
			quickSort(array,q+1,r);
		}
	}
	public static int partition(double[] array,int p, int r){
		double x=array[p];
		int i=p-1;
		int j=r+1;
		while(true){
			i++;
			while(i<r && array[i]<x)
				i++;
			j--;
			while(j>p && array[j]>x)
				j--;
			if(i<j)
				exchange(array,i,j);
			else
				return j;
		}
	}
	public static void mergeSort(double[] array,int l,int n){
		int low=l;
		int high=n;
		if(low>=high){
			return;
		}
		int mid=(low+high)/2;
		mergeSort(array,low,mid);
		mergeSort(array,mid+1,high);
		int elow=mid;
		int shigh=mid+1;
		while((l<=elow)&&(shigh<=high)){
			if(array[low]<array[shigh]){
				low++;
			}
			else{
				double temp=array[shigh];
				for(int k=shigh-1;k>=low;k--){
					array[k+1]=array[k];
				}
				array[low]=temp;
				low++;
				elow++;
				shigh++;
			}
		}
	}
	
	
	public static int linearSearch(int[] arr, int key){
		int pos=-1;
		for(int i=0;i<arr.length;i++)
			if(arr[i]==key){
				pos=i+1;
				System.out.println("the key element"+key+"is present in the position"+pos);				
			}
		return pos;	
	}
	public static int binarySearch(int[] arr, int k){
		int pos=-1;
		int low =0;
		int high=arr.length-1;
		int mid=(low+high)/2;
		while(low<=high){
			mid=(low+high)/2;
			if(k<arr[mid])
				high=mid-1;
			else{
				pos=mid+1;
				break;
			}
		}
		System.out.println("the key element"+k+"is present in the position"+pos);
		return pos;
	}
}